package com.ma.heap;

import static com.ma.tool.system.basics.swap;

public class maxHeap {


    private int[] heap;
    private final int limit;
    private int heapSize;


    public maxHeap(int limit) {
        heap=new int[limit];
        this.limit = limit;
        this.heapSize = 0;
    }
    //是否空
    public boolean isEmpty(){
        return heapSize==0;
    }

    //是否满
    public boolean isFull(){
        return heapSize==limit;
    }


    /**
     * 添加
     * @param value
     */
    public void push(int value){
        if(heapSize==limit){
            throw new RuntimeException("full!!!");
        }
        heap[heapSize]=value;
        heapInsert(heap,heapSize++);
    }

    /**
     * 删除
     * @return 删除的指
     */
    public int pop(){
        int ans=heap[0];
        swap(heap,0,--heapSize);
        heapify(heap,0,heapSize);
        return ans;
    }
    /**
     * 大根堆添加操作
     * @param arr
     * @param index
     */
    private static void heapInsert(int[] arr,int index){
        //只有arr[index]大于父节点时才上升，父节点下沉
        while (arr[index]>arr[(index-1)>>1]){
            swap(arr,index,(index-1)>>1);
            index=(index-1)>>1;
        }
    }

    /**
     * 大根堆下沉操作
     * @param arr
     * @param index
     * @param heapSize
     */
    private static void heapify(int[] arr,int index,int heapSize){
        int left=index*2+1;//左孩子
        while (left<heapSize){
            //判断啊当前（index）节点的子节点相互比较，左节点一定存在，判断右节点是否存在且大于左节点
            int largest=(left+1)<heapSize&&arr[left + 1]>arr[left]?left+1:left;
            //判断最大的子节点是否比父节点（index）大，把大的记录下来
            largest=arr[largest]>arr[index]?largest:index;

            //如果子节点都小于父节点，则不需要下沉
            if(largest==index){
                break;
            }
            //交换大子节点与父节点
            swap(arr, index, largest);
            //变换父节点，继续循环，继续看是否需要继续下沉
            index=largest;
            left=index*2+1;

        }
    }

}
